package tree.binarysearchtree;

import tree.TreeNode;

/**
 * @Classname : ConvertBstToGreaterTree
 * @Description :
 * <a href="https://leetcode.cn/problems/convert-bst-to-greater-tree/">538. 把二叉搜索树转换为累加树</a>
 * @Author : chentianyu
 * @Date 2023/1/21 09:42
 */


public class ConvertBstToGreaterTree {

    private int sum = 0;

    /**
     * 反向中序遍历+全局变量实现
     *
     * @param root
     * @return
     */
    public TreeNode convertBST(TreeNode root) {
        if (root == null) return null;

        convertBST(root.right);
        sum += root.val;
        root.val = sum;
        convertBST(root.left);
        return root;
    }
}
